## Complexité des algorithmes

## Introduction

Pour résoudre un problème, il peut y avoir plusieurs solutions plus ou moins efficaces :

- du point de vue de l'utilisation de la mémoire
- du point de vue du temps de calcul.

On parle de coût ou de complexité mémoire / temporelle.

La complexité mesure l'efficacité d'un algorithme. Elle est indiquée en **O**rdre 
de grandeur, en fonction de la taille des données, par convention appelée **n**.

Différentes complexités existent, celle du meilleur cas, la moyenne, mais 
celle qui est habituellement retenue comme mesure de l'efficacité de l'algorithme 
est celle du **pire cas**.

Pour la complexité en temps de calcul, il est possible de compter le nombre 
de comparaisons ou d'affectations par exemple, ou encore le nombre d'itérations.
*En pratique, on choisi de dénombrer l'instruction qui s'exécute le plus.*

Souvent, il faut faire un compromis entre le coût en temps et en mémoire.


## Le logarithme en base 2

Le logarithme en base 2 est utilisé pour exprimer certaines complexité. Il
est défini comme suit : `log2(n) = ln(n) / ln(2)` ; exemple : `log2(100) = 6,64…`. 
Retenir la valeur arrondie à l'entier supérieur ; elle correspond :

- au nombre de fois qu'il faut diviser un nombre par 2 pour obtenir une valeur
inférieure ou égale à 1 ; exemple : 100 / 2 = 50 ; 50 / 2 = 25… (7 divisions) ;
- ou encore, à la (première) puissance de 2 supérieure au nombre : 2^7^ = 128.


## Différents ordres des grandeur

- Lorsque la complexité ne dépend pas de la taille des données, on est en **0(1)** ;
exemple : accéder au i-ème élément d'un tableau (complexité **constante**).
- une recherche dichotomique (dans un tableau trié) est en **O(log2(n))**
complexité **logarithmique**).
- Pour parcourir un tableau de taille "n", il faut "n" itérations, ce qui
correspond à une complexité en **0(n)** (complexité **linéaire**) ;
- un algorithme de tri à une complexité
	- en **O(n²)** ; exemples : tri bulle, par insertion ou par sélection
	(complexité **quadratique**) ;
	- en **O(n.log2(n))** ; exemples : tri rapide, par tas ou fusion.

*Remarque : il existe d'autres formes de  complexité (extrêmement coûteuses) :
cubique, factorielle et polynomiale*.

| Complexité théorique  | `0(1)` | `0(log2(n))` | `0(n)` | `0(n.log2(n))` | `0(n²)` |
| --------------------- | ------ | ------------ | ------ | -------------- | ------- |
| Exemple pour n = 100  | 1      | 7            | 100    | 700            | 10000   |
| Exemple pour n = 1000 | 1      | 10           | 1000   | 10000          | 1000000 |